Formuła 1

Limit pamięci: 128 MB

Mały Robert Kubita bardzo lubi oglądać wyścigi Formuły 1, które w Bajtocji odbywają się na torze prowadzącym z Bajtogrodu do Bitowic. Najbardziej ekscytującymi dla Roberta momentami wyścigu są manewry wyprzedzania, dlatego chłopiec chciałby ich widzieć jak najwięcej.

Marzy mu się zobaczyć wyścig, który spełniłby następujące założenia: ścigałoby się w nim bolidów, a dla każdego () bolid, który startował z -tej pozycji, wykonałby podczas wyścigu manewrów wyprzedzania. Zakładamy, że w każdej chwili wyścigu odbywa się co najwyżej jeden manewr wyprzedzania, który polega na tym, że pewien bolid przesuwa się przed bolid bezpośrednio poprzedzający go.

Robert zastanawia się, czy taki wyścig jest w ogóle możliwy. Poprosił Cię o pomoc w rozstrzygnięciu tej kwestii.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita , oznaczająca liczbę zestawów testowych opisanych w dalszej części wejścia.

Opis każdego zestawu składa się z dwóch wierszy. W pierwszym z nich znajduje się jedna liczba całkowita (), oznaczająca liczbę bolidów biorących udział w wyścigu. W drugim wierszu znajduje się ciąg liczb całkowitych (), który zadaje, ile manewrów wyprzedzania muszą wykonać poszczególne bolidy.

Rozmiar żadnego pliku wejściowego nie przekracza 20 MB.

Wyjście

Twój program powinien wypisać wierszy z odpowiedziami dla kolejnych zestawów testowych. Odpowiedzią dla zestawu jest słowo TAK albo NIE, w zależności od tego, czy da się zrealizować wyścig zgodnie z wytycznymi Roberta.

Przykład

Dla danych wejściowych:

3
2
0 1
3
0 1 4
3
1 1 3

poprawną odpowiedzią jest:

TAK
NIE
TAK

Autor zadania: Tomasz Idziaszek.